class Solution(object):
    def openLock(self, deadends, target):
        """
        :type deadends: List[str]
        :type target: str
        :rtype: int
        """
        if target == '0000':
            return 0
        a_set = {'0000', target}
        start_st = {'0000'}
        end_st = {target}
        dead_st = set(deadends)
        if '0000' in dead_st:
            return -1
        state = 0
        dist = 0

        def find_next(s):
            out = set()
            for i in range(4):
                out.add(s[:i] + chr((ord(s[i]) - ord('0') + 1) % 10 + ord('0')) + s[i + 1:])
                out.add(s[:i] + chr((ord(s[i]) - ord('0') - 1) % 10 + ord('0')) + s[i + 1:])
            return out

        while start_st and end_st:
            dist += 1
            if state == 0:
                next_st = set()
                for point in start_st:
                    wait = find_next(point)
                    for p in wait:
                        if p not in dead_st:
                            if p in end_st:
                                return dist
                            if p not in a_set:
                                next_st.add(p)
                                a_set.add(p)
                start_st = next_st
                state = 1
            else:
                next_st = set()
                for point in end_st:
                    wait = find_next(point)
                    for p in wait:
                        if p not in dead_st:
                            if p in start_st:
                                return dist
                            if p not in a_set:
                                next_st.add(p)
                                a_set.add(p)
                end_st = next_st
                state = 0
        return -1


data = Solution()
deadends = ["0201", "0101", "0102", "1212", "2002"]
target = "0202"
print(data.openLock(deadends, target))
